package main

func main() {

}

func maxDepth(root *TreeNode) int {

	depth := 0

	if root == nil {
		return depth
	}

	var dp func(node *TreeNode, depth int)
	m := make(map[int]int)

	dp = func(node *TreeNode, depth int) {
		if node == nil {
			return
		}

		if _, ok := m[depth]; ok {
			m[depth]++
		} else {
			m[depth] = 1
		}

		depth++
		dp(node.Left, depth)
		dp(node.Right, depth)
	}

	dp(root, 0)
	return len(m)
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
